A processor manipulates and controls the flow of data in a computer system. Increasing the speed and decreasing the size of the processor will tend to increase the computational power of the computer and decrease its manufacturing cost. Processor designers employ many different techniques to increase processor speed and decrease size to create more powerful and less expensive computers for consumers. One such technique involves partitioning the memory of a computer system into hierarchical levels to improve data retrieval efficiency.
A computer uses memory to store data that may be needed by the processor at a future time. Computer memory is divided into a number of memory arrays in a memory hierarchy. According to the memory hierarchy, data that the processor will more likely use in the near future is stored in a memory array that occupies a hierarchical level closer to the processor. Data that the processor will less likely need in the near future is stored in a memory array that occupies a hierarchical level further from the processor. In this manner, data processing efficiency is improved because the more frequently used data can be more quickly accessed by the processor than the less frequently used data.
The tradeoff for quick access to data stored in a memory array close to the processor is that this array tends to be smaller than a memory array further from the processor. The memory array close to the processor is made smaller to reduce the cost of manufacturing and to boost the access speed of the array. For example, some memory arrays that are close to the processor reside on the same semiconductor substrate as the processor. Increasing the size of such an array increases the size of the processor, making the processor more expensive. In addition, the processor will take longer to access the larger array because it has more data to search through. To address this tradeoff between the speed of access of a memory array versus the size of the memory array, various algorithms are employed to better distinguish between data that will most likely be soon accessed by the processor versus data that will least likely be soon accessed.
A memory array typically comprises data arranged in data lines that are accessed, or "used", by the processor. A line replacement algorithm tracks the lines of a memory array such that a line that is less likely to be soon used is, ideally, replaced with a line that is more likely to be soon used. One of the most accurate predictors of whether a line is likely to be soon used by the processor is how recently the line was used in the past. A line that was recently used will more likely be soon used again than a line that was not recently used.
One line replacement algorithm is called a not recently used (NRU) algorithm. In an NRU algorithm, each line of a memory array has a corresponding NRU bit in an NRU table that indicates line usage. When a line is used by the processor, its corresponding NRU bit is set to a value that indicates that the line has recently been used. Once all the NRU bits of the memory array have been set to a value that indicates that their corresponding lines have recently been used, all the NRU bits are reset. Resetting the NRU bits changes the value of the NRU bits to indicate that the lines have not recently been used. This changes the status of all the lines to NRU lines. When the processor needs to replace a line in the array with new data, the processor searches for and replaces a NRU line with the new data.
One problem with the NRU line replacement algorithm is that the moment the NRU bits are reset, there is no longer any indication as to which line has recently been used. As a result, the processor might replace a more recently used line, rather than a less recently used line, with new data, causing inefficient use of the memory array. In addition, the NRU algorithm can be time consuming for large memory arrays due to the time it takes to search large arrays for an NRU line.
An alternative line replacement algorithm is called a least recently used (LRU) algorithm. In an LRU algorithm, each line of a memory array has a corresponding entry in an LRU table that indicates line usage. When a line is used by the processor, its corresponding LRU table entry is set to a value that indicates that the line has been most recently used. When this line is set to a most recently used status, the previous most recently used line is set to a second most recently used status. The previous second most recently used line is set to a third most recently used status. The previous third most recently used line is set to a fourth most recently used status. And so forth. When the processor needs to replace a line in the array with new data, the processor searches for and replaces the least most recently used line (the LRU line), indicated by the value of its LRU table entry.
One problem with the LRU line replacement algorithm is that it is expensive to implement because it requires a lot of memory and logic space. Each entry in the LRU table comprises numerous bits for each line, and several entries in the table may be modified each time a new line is elevated to most recently used status. This requires quite a bit of data manipulation.